package org.example;

import java.util.ArrayList;
import java.util.List;

public class Test5 {
    //leetcode 763 划分字母区间

    /**
     * 先遍历一遍数组，将数组中每个字母出现的最后一个位置记录下来
     * 然后在遍历一遍数组，用start记录子字符串的开始位置，end记录字符串中的所有字母中出现的最后的位置，
     * 当到达这个最后的位置end的时候，将end-start添加进去list中
     * @param s
     * @return
     */
    public List<Integer> partitionLabels(String s) {
        int[] hash = new int[26];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            hash[s.charAt(i) - 'a'] = i;
        }
        int end = 0,start = 0;
        int index = 0;
        List<Integer> ret = new ArrayList<>();
        while (index < n) {
            start = index;
            end = hash[s.charAt(index) - 'a'];
            while (index < n && index < end) {
                end = Math.max(end,hash[s.charAt(index) - 'a']);
                index++;
            }
            index++;
            ret.add(end - start + 1);
        }
        return ret;
    }

    public static void main(String[] args) {
        Test5 test5 = new Test5();
        String s = "ababcbacadefegdehijhklij";
        test5.partitionLabels(s);
        System.out.println(444);
    }
}
